//Letter Combinations of a Phone Number 
/*
#include <time.h>
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#include <iostream>
using namespace std;
string findNum(int d){
	switch (d)
	{
	case 0:
	case 1:return "";
	case 2:return "abc";
	case 3:return "def";
	case 4:return "ghi";
	case 5:return "jkl";
	case 6:return "mno";
	case 7:return "pqrs";
	case 8:return "tuv";
	case 9:return "wxyz";
	default:return "";
	}
}
void gene(vector<string>&re,string pre,string digits){
	if(digits.length()<1){
		re.push_back(pre);
		//cout<<pre<<endl;
	}
	else{
			int d=digits.at(0)-'0';
			string str=findNum(d);
			string tmp="";
			string sub=digits.substr(1,digits.length()-1);
			if(str==""){
				gene(re,pre,sub);
			}
			for(int k=0;k<str.length();k++){
				tmp=pre+str.at(k);
				gene(re,tmp,sub);
			}
	}
}
vector<string> letterCombinations(string digits) {
	vector<string> re;
	if(digits.length()<1)
		return re;
	gene(re,"",digits);
	return re;
}
int main(){
	string p;
	int a[]={-1,2,1,-4};
	vector<int>v1(a,a+sizeof(a)/sizeof(int));
	vector<string> re=letterCombinations("");
	for(int i=0;i<re.size();i++)
		cout<<re[i]<<endl;
	system("pause");
	return 0;
}
*/